package com.ztom.top100;

import java.util.Arrays;

/**
 * 最长无重复子串
 * <p>
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 *
 * @author ZhangTao
 */
public class Code03LengthOfLongestSubstring {

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        char[] str = s.toCharArray();
        // 记录字符上次出现的位置,  字符 char 长度 128
        int[] index = new int[128];
        Arrays.fill(index, -1);
        int max = 0;
        // 左指针
        int l = 0;
        for (int r = 0; r < str.length; r++) {
            // 考察右指针位置的字符是否出现过
            // 如果未出现过, 左指针不变化
            // 如果出现过, 左指针指向上次出现位置的下一个位置
            l = Math.max(l, index[str[r]] + 1);
            // 记录最大长度
            max = Math.max(max, r - l + 1);
            // 记录当前字符出现过的位置
            index[str[r]] = r;
        }
        return max;
    }
}
